package leetCode.solution;

import com.alibaba.fastjson.JSON;

/**
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 * 
 * @author jerry
 * @ClassName: Solution338
 * @Description:TODO(描述这个类的作用)
 * @date 2022年11月22日 下午2:19:29
 */
public class Solution338 {
	public static void main(String[] args) {
		System.out.println(JSON.toJSONString(new Solution338().countBits(115)));
		System.out.println(JSON.toJSONString(new Solution338().countBits2(115)));
		System.out.println(JSON.toJSONString(new Solution338().countBits4(115)));
		System.out.println(JSON.toJSONString(new Solution338().countBits5(115)));
	}

	public int[] countBits(int n) {
		int[] arr = new int[n + 1];
		arr[0] = 0;
		arr[1] = 1;
		arr[2] = 1;
		for (int i = 2; i <= n; i++) {
			arr[i] = Integer.bitCount(i);
		}
		return arr;
	}

	public int[] countBits3(int n) {
		int[] arr = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			arr[i] = Integer.bitCount(i);
		}
		return arr;
	}

	public int[] countBits2(int n) {
		int[] arr = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			arr[i] = mybitCount3(i);
		}
		return arr;
	}

	private int mybitCount(int i) {
		int count = 0;
		while (i > 0) {
			if ((i & 1) == 1) {
				count += (i & 1) == 1 ? 1 : 0;
			}
			i = i >> 1;
		}
		return count;
	}

	/**
	 * 0xaaaaaaaa = 10101010101010101010101010101010 (偶数位为1，奇数位为0）
	 * 
	 * 0x55555555 = 1010101010101010101010101010101 (偶数位为0，奇数位为1）
	 * 
	 * 0x33333333 = 110011001100110011001100110011 (1和0每隔两位交替出现)
	 * 
	 * 0xcccccccc = 11001100110011001100110011001100(0和1每隔两位交替出现)
	 * 
	 * 0x0f0f0f0f = 00001111000011110000111100001111 (1和0每隔四位交替出现)
	 * 
	 * 0xf0f0f0f0 = 11110000111100001111000011110000 (0和1每隔四位交替出现)
	 * 
	 * 0x3f = 111111 (确保32位大小)
	 * @author jerry
	 * @date 2022年11月23日 上午10:07:26
	 * @param
	 * @return
	 */
	private int mybitCount4(int i) {
		i = i - ((i >>> 1) & 0x55555555);
		i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
		i = (i + (i >>> 4)) & 0x0f0f0f0f;
		i = i + (i >>> 8);
		i = i + (i >>> 16);
		return i & 0x3f;
	}

	public int mybitCount2(int x) {
		int ones = 0;
		while (x > 0) {
			x &= (x - 1);
			ones++;
		}
		return ones;
	}

	private int mybitCount3(int i) {
		int count = 0;
		while (i > 0) {
			i = i ^ (i & ((~i + 1)));
			count += 1;
		}
		return count;
	}

	public int[] countBits4(int n) {
		int[] bits = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			bits[i] = bits[i & (i - 1)] + 1;
		}
		return bits;
	}

	public int[] countBits5(int n) {
		int[] bits = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			bits[i] = bits[i ^ (i & ((~i + 1)))] + 1;
		}
		return bits;
	}

	public int[] countBits6(int n) {
		int[] bits = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			bits[i] = bits[i >> 1] + (i & 1);
		}
		return bits;
	}

	public int[] countBits7(int n) {
		int[] bits = new int[n + 1];
		int highBit = 0;
		for (int i = 1; i <= n; i++) {
			if ((i & (i - 1)) == 0) {
				highBit = i;
			}
			bits[i] = bits[i - highBit] + 1;
		}
		return bits;
	}

}
